; Exercicio 1.19

; T_11(a,b) = (a+b,a)
; T_pq(a,b) = (bq+aq+ap,bp+aq)

; Queremos calcular T_pq^2(a,b).
; T_pq(T_pq(a,b)) = T_pq(bq + aq + ap , bp + aq)
;            = T_pq(a',b') [onde a'=bq+aq+ap e b'=bp+aq]
;            = (b'q + a'q + a'p , b'p + a'q) [substituindo a' e b' e trabalhando os termos no papel...]
;            = (bq' + aq' + ap' , bp' + aq') [onde q' = 2pq+q^2 e p' = p^2+q^2]

(define (fib n)
  (fib-iter 1 0 0 1 n))
(define (fib-iter a b p q count)
  (cond ((= count 0) b)
        ((even? count)
         (fib-iter a
                   b
                   (+ (* p p) (* q q))
                   (+ (* 2 p q) (* q q))
                   (/ count 2)))
        (else (fib-iter (+ (* b q) (* a q) (* a p))
                        (+ (* b p) (* a q))
                        p
                        q
                        (- count 1)))))